Foreword
Creative Scala is aimed at developers who have no prior experience in Scala. It is designed to give you a fun introduction to functional programming. We assume you have some familiarity with another programming language but little or no experience with Scala or other functional languages.
Our goal is to demonstrate the building blocks that Scala developers use to create programs in a clear, succinct, declarative manner. Working through the exercises in the book should take a few hours, after which we hope you will have a feel of what Scala can do for your applications.
Although this book will give you the basic mental model required to become competent with Scala, you won’t finish knowing everything you need to be self-sufficient. For further advancement we recommend considering one of the many excellent Scala textbooks out there, including our own Essential Scala.
If you are working through the exercises on your own, we highly recommend joining our Gitter chat room to provide get help with the exercises and provide feedback on the book.
The text of Creative Scala is open souce, as is the source code for the Doodle drawing library used in the exercises. You can grab the code from our Github account. Contact us on Gitter or by email if you would like to contribute.
Thanks for downloading and happy creative programming!
—Dave and Noel
Notes on the Early Access Edition
This is an early access release of Creative Scala. This means there are unfinished aspects as detailed below. There may be typos and errata in the text and examples.
If you spot any mistakes or would like to provide feedback, please let us know via our Gitter chat room or by email:
- Dave Gurnell ()
- Noel Welsh ()
Acknowledgements
Creative Scala was written by Dave Gurnell and Noel Welsh. Many thanks to Richard Dallaway, Jonathan Ferguson, and the team at Underscore for their invaluable contributions and extensive proof reading.
Thanks also to the many people who pointed out errors or made suggestions to improve the book: Neil Moore, and many more for whom we didn’t record the name.
1 Getting Started
Installing required software - Text editor and SBT OR IntelliJ and SBT plugin - Doodle skeleton
Run a simple program to check everything works.
2 Expressions, Values, and Types
Scala programs have three fundamental building blocks: expressions, values, and types. In this section we explore these concepts.
Here’s a very simple expression:
1 + 2An expression is a fragment of Scala code. We can write expressions in an a text editor, or on a piece of paper, or on a wall. You get the idea.
Expressions are like writing. Just like writing must be read for it to have any effect on the world (and the reader has to understand the language the writing is written in), the computer must run an expression for it to have an effect. The result of running an expression is a value. Value’s live in the computer’s memory, in the same way that the result of reading some writing lives in the reader’s head. We will also say expressions are evaluated or executed to describe the process of transforming them into values.
We can evaluate expressions immediately by writing them at the console and pressing “Enter” (or “Return”). Try it now.
1 + 2
The console responds with the value the expression evaluates to, and the type of the expression.
The expression 1 + 2 evaluates to the value 3. We can write down the number three here on the page, but the real value is something stored in the computer’s memory. In this case, it is a 32-bit integer represented in two’s-complement. The meaning of “32-bit integer represented in two’s-complement” is not important. I just mention it to emphasise the fact the computer’s representation of the value 3 is the true value, not the numeral written here or by the console.
Types are the final piece of the puzzle. A type is anything we can determine about a program without running it. The expression 1 + 2 has the type Int, which means we should interpret the value the expression evaluates to as an integer. This further means we can write further expressions that make sense for integers with the expression result of this expression. We could add, subtract, multiply, or divide, but we couldn’t convert it to lowercase, for example.
Types will often tell us how we should understand the value (the “stuff” in the computer’s memory) that an expression evaluates to. Should we understand it as an integer or as a stream of points giving the current position of the mouse? The types will tell us. We can use types for other things, including things that don’t have any representation at run-time. These uses are a bit more advanced than we’ll get into here, but don’t make the mistake of thinking that types correspond to value. Types only exist at compile-time in Scala. There is not necessarily any representation at runtime of the type of the expression that produced a given a value.
Before a Scala program is run, it must be compiled. Compilation checks that a program makes sense. It must be syntactically correct, meaning it must be written according to the rules of Scala. For example (1 + 2) is syntactically correct, but (1 + 2 is not. It must also type check, meaning the types must be correct for the operations we’re trying to do. 1 + 2 type checks (we are adding integers), but 1.toUpperCase does not (there is no concept of upper and lower case for numbers.)
Only programs that successfully compile can be run. We can think of compilation as being analogous to the rules of grammar in writing. The sentence “F$Rf fjrmn;l df.fd” is syntactically incorrect in English. The arrangement of letters doesn’t form any words. The sentence “dog fly a here no” is made out of valid words but their arrangement breaks the rules of grammar—analogous to the type checks that Scala performs.
We will talk about compile-time as the time when a code is compiled, and run-time as the time when the code is run.
2.1 Literal Expressions
We’ll now start to explore the various forms of expressions in Scala, starting with the simplest expressions literals. Here’s a literal expression:
3
A literal evaluates to “itself.” How we write the expression and how the console prints the value are the same. Remember though, there is a difference between the written representation of a value and its actual representation in the computer’s memory.
Scala has many different forms of literals. We’ve already seen Int literals. There is a different type, and a different literal syntax, for what are called floating point numbers. This corresponds to a computer’s approximation of the real numbers. Here’s an example:
0.1
As you can see, the type is called Double.
Numbers are well and good, but what about text. Scala’s String type represents a sequence of characters. We write literal strings by putting their contents in double quotes.
"To be fond of dancing was a certain step towards falling in love."
Sometimes we want to write strings that span several lines. We can do this by using triple double quotes, as below.
"""
A new, a vast, and a powerful language is developed for the future use of analysis,
in which to wield its truths so that these may become of more speedy and accurate
practical application for the purposes of mankind than the means hitherto in our
possession have rendered possible.
-- Ada Lovelace, the world's first programmer
"""
A String is a sequence of characters. Characters themselves have a type, Char, and character literals are written in single quotes.
'a'
Finally we’ll look at the literal representations of the Boolean type, named after English logician George Boolean. The fancy name just means a value that can be either true or false, and this indeed is how we write boolean literals.
true
false
With literal expressions we can create values, but we won’t get very far if we can’t somehow interact with the values we’ve created. We’ve seen a few examples of more complex expressions like 1 + 2. In the next section we’ll learn about objects and methods, which will allow to understand how this, and more interesting expressions, work.
2.2 Values are Objects
In Scala all values are objects. An object is a grouping of data and operations on that data. For example, 2 is an object. The data is the integer 2, and the operations on that data are familiar operations like +, -, and so on. We call operations of an object the object’s methods.
2.2.1 Method Calls
We interact with objects by calling or invoking methods. For example, we can get the uppercase version of a String by calling its toUpperCase method.
"Titan!".toUpperCase
Some methods accept parameters or arguments, which control how the method works. The take method, for example, takes characters from a String. We must pass a parameter to take to specify how many characters we want.
"Gilgamesh went abroad in the world".take(3)
"Gilgamesh went abroad in the world".take(9)
A method call is an expression, and thus evaluates to an object. This means we can chain method calls together to make more complex programs:
"Titan!".toUpperCase.toLowerCase
Method Call Syntax
The syntax for a method call is
anExpression.methodName(param1, ...)or
anExpression.methodNamewhere
anExpressionis any expression (which evaluates to an object)methodNameis the name of the method- the optional
param1, ...are one or more expressions evaluating to the parameters to the method.
2.2.2 Operators
We have said that all values are objects, and we call methods with the syntax object.methodName(parameter). How then do we explain expressions like 1 + 2?
In Scala, and expression written a.b(c) can be written a b c. So these are equivalent:
1 + 2
1.+(2)
This second way of calling a method is known an operator style.
Infix Operator Notation
Any Scala expression written a.b(c) can also be written a b c.
Note that a b c d e is equivalent to a.b(c).d(e), not a.b(c, d, e).
2.3 Types
Now we can write more complex expressions we can talk a little more about types.
One use of types is stopping us from calling methods that don’t exist. The type of an expression tells the compiler what methods exist on the value it evaluates to. Our code won’t compile if we try to call to a method that doesn’t exist. Here are some simple examples.
"Brontë" / "Austen"
1.take(2)
It really is the type of the expression that determines what methods we can call, which we can demonstrate by calling methods on the result of more complex expressions.
(1 + 3).take(1)
This process of type checking also applies to the parameter of methods.
1.min("zero")
Types are a property of expressions and thus exist at compile-time (as we have discussed before.) This means we can determine the type of expression even if evaluating it results in an error at run-time. For example, dividing an Int by zero causes a run-time error.
1 / 0
The expression 1 / 0 still has a type, and we can get that type from the console as shown below.
:type 1 / 0
// IntWe can also write a compound expression including a sub-expression that will fail at run-time.
(2 + (1 / 0) + 3)
This expression also has a type.
:type (2 + (1 / 0) + 3)
// Int2.4 Exercises
2.4.0.1 Arithmetic
Write an expression using integer literals, addition, and subtraction that evaluates to 42.
This exercise is just about getting used to writing Scala code. Here is one possible solution.
1 + 43 - 2
2.4.0.2 Appending Strings
Join together two strings (known as appending strings) using the ++ method. Write equivalent expressions using both the normal method call style and operator style.
Something like the below should do.
"It is a truth ".++("universally acknowledged")
"It is a truth " ++ "universally acknowledged"
2.4.0.3 Precedence
In mathematics we learned that some operators take precedence over others. For example, in the expression 1 + 2 * 3 we should do the multiplication before the addition. Do the same rules hold in Scala?
A bit of exploration at the console should convince you that yes, Scala does maintain the standard precedence rules. The example below demonstrates this.
1 + 2 * 3
1 + (2 * 3)
(1 + 2) * 3
2.4.0.4 Types and Values
Which of the following expressions will not compile? Of the expressions that will compile, what is their type? Which expressions fail at run-time?
1 + 2
"3".toInt
"Electric blue".toInt
"Electric blue".take(1)
"Electric blue".take("blue")
1 + ("Moonage daydream".indexOf("N"))
1 / 1 + ("Moonage daydream".indexOf("N"))
1 / (1 + ("Moonage daydream".indexOf("N")))
1 + 2
This expression has type Int and evaluates to 3.
"3".toInt
This expression has type Int and evaluates to 3.
"Electric blue".toInt
This expression has type Int but fails at run-time.
"Electric blue".take(1)
This expression has type String and evaluates to "E".
"Electric blue".take("blue")
This expression fails at compile-time and hence has no type.
1 + ("Moonage daydream".indexOf("N"))
This expression has type Int and evaluates to 0.
1 / 1 + ("Moonage daydream".indexOf("N"))
This expression has type Int and, due to precedence, evaluates to (1 / 1) + -1, which is 0.
1 / (1 + ("Moonage daydream".indexOf("N")))
This expression has type Int but fails at run-time with a division by zero.
2.4.0.5 Floating Point Failings
When we introduced Doubles, I said they are an approximation to the real numbers. Why do you think this is? Think about representing numbers like ⅓ and π. How much space would it take to represent these numbers in decimal?
Double is an approximation because it has the fit within the computer’s finite memory. A Double takes up precisely 64-bits, which is enough space to store a lot of digits but not enough to store a number that, like π, has an infinite expansion.
The number ⅓ also has an infinite expansion in decimal. As Doubles are stored in binary there are some numbers that can be represented in a finite number of decimal digits but have no finite representation in binary. 0.1 turns out to be one such number.
In general, floating point numbers can lead to nasty surprises if you expect them to act like the reals. They are fine for our purposes in Creative Scala, but don’t go using them to write accounting software!
2.4.0.6 Beyond Expressions
In our current model of computation there are only three components: expressions (program text) with types, that evaluate to values (something within the computer’s memory). Is this sufficient? Could we write a stock market or a computer game with just this model? Can you think of ways to extend this model?
This is very open ended question. There are several ways to go beyond the model we have so far.
To be useful our programs must be capable of creating effects—changes in the world that go beyond the computer’s memory. For example, displaying things on the screen, making sound, sending messages to other computers, and the like. The console implicitly does some of this for us, by printing values on the screen. We’ll need to go a bit beyond that for more useful programs.
We also don’t have any way to define our own objects and methods, or reuse values in our programs. If we want to, say, use someone’s name across a program we have to repeat that name everywhere. We need more methods of abstraction and that’s what we’ll turn to soon.
3 Computing With Pictures
So far we have computed using numbers, strings, and other simple objects. This is not particularly interesting. From here on out we will focus our attention to computing with pictures, and later to animations. Pictures offer us more immediate creative opportunities, and they make our program output tangible in a way that other methods can’t deliver.
We’ll use a library called Doodle to help us with creating graphics. In this chapter we will learn the basics of Doodle.
If you run the examples from the SBT console within Doodle they will just work. If not, you will need to start your code with the following imports to make Doodle available.
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
3.1 Images
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
Let’s start with some simple shapes, programming at the console as we’ve done before.
Image.circle(10)
What is happening here? Image is an object and circle a method on that object. We pass to circle a parameter, 10 that gives the radius of the circle we’re constructing. Note the type of the result—an Image.
We can also write just circle(10), as if you run the console within Doodle it automatically makes this and other methods to construct images available.
circle(10)
We draw the circle by calling the draw method.
circle(10).drawA window should appear as shown in fig. 1.
Figure 1: A circle
Doodle supports a handful of “primitive” images: circles, rectangles, and triangles. Let’s try drawing a rectangle.
rectangle(50, 100).drawThe output is shown in fig. 2.
Figure 2: A rectangle
Finally let’s try a triangle, for which the output is shown in fig. ??.
triangle(60, 40).drawA triangle
Exercises
I Go Round in Circles
Create circles that are 1, 10, and 100 units wide. Now draw them!
In this exercise we’re checking that our Doodle install is working correctly and we’re getting used to using the library. One of the important points in Doodle is we separate defining the image from drawing the image. We’ll talk more about this throughout the book.
We can create circles with the code below.
circle(1)
circle(10)
circle(100)
We can draw the circles by calling the draw method on each circle.
circle(1).draw
circle(10).draw
circle(100).drawMy Type of Art
What is the type of a circle? A rectangle? A triangle?
They all have type Image, as we can tell from the console.
:type circle(10)
// doodle.core.Image
:type rectangle(10, 10)
// doodle.core.Image
:type triangle(10, 10)
// doodle.core.ImageNot My Type of Art
What’s the type of drawing an image? What does this mean?
Once again, we can ask the console this quesstion.
:type circle(10).draw
// UnitWe see that the type of drawing an image is Unit. Unit is the type of expressions that have no interesting value to return. This is the case for draw; we call it because we want something to appear on the screen, not because we have a use for the value it returns. There is only one value with type Unit. This value is also called unit, which written as a literal expression is ()
You’ll note that the console doesn’t print unit by default.
()We can ask the console for the type to show that there really is unit here.
:type ()
// Unit3.2 Layout
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
We can seen how to create primitive images. We can combine together images using layouts methods to create more complex images. Try the following code—you should see a circle and a rectangle displayed beside one another, as in fig. 3.
(circle(10) beside rectangle(10, 20)).drawFigure 3: A circle beside a rectangle
Doodle contains several layout methods for combining images, described in tbl. 1. Try them out now to see what they do.
| Operator | Type | Description | Example |
|---|---|---|---|
Image beside Image |
Image |
Places images horizontally next to one another. | circle(10) beside circle(20) |
Image above Image |
Image |
Places images vertically next to one another. | circle(10) above circle(20) |
Image below Image |
Image |
Places images vertically next to one another. | circle(10) below circle(20) |
Image on Image |
Image |
Places images centered on top of one another. | circle(10) on circle(20) |
Image under Image |
Image |
Places images centered on top of one another. | circle(10) under circle(20) |
Exercises
The Width of a Circle
Create the picture fig. 4 using the layout methods and basic images we’ve covered so far.
Figure 4: The width of a circle
It’s three small circles on top of a bigger circle, and we can just about state this as is in code.
(circle(20) beside circle(20) beside circle(20)) on circle(60)
3.3 Color
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
In addition to layout, Doodle has some simple operators to add a splash of colour to our images. Try these out the methods described in tbl. 2 to see how they work.
| Operator | Type | Description | Example |
|---|---|---|---|
Image fillColor Color |
Image |
Fills the image with the specified colour. | circle(10) fillColor Color.red |
Image lineColor Color |
Image |
Outlines the image with the specified colour. | circle(10) lineColor Color.blue |
Image lineWidth Int |
Image |
Outlines the image with the specified stroke width. | circle(10) lineWidth 3 |
Doodle has various ways of creating colours. The simplest are the predefined colours in CommonColors.scala. Some of the most commonly used are described in tbl. 3.
| Color | Type | Example |
|---|---|---|
Color.red |
Color |
circle(10) fillColor Color.red |
Color.blue |
Color |
circle(10) fillColor Color.blue |
Color.green |
Color |
circle(10) fillColor Color.green |
Color.black |
Color |
circle(10) fillColor Color.black |
Color.white |
Color |
circle(10) fillColor Color.white |
Color.gray |
Color |
circle(10) fillColor Color.gray |
Color.brown |
Color |
circle(10) fillColor Color.brown |
3.3.0.1 Exercise
3.3.0.1.1 Evil Eye
Make the image in fig. 5, designed to look like a traditional amulet protecting against the evil eye. I used cornflowBlue for the iris, and darkBlue for the outer color, but experiment with your own choices!
Figure 5: No evil eyes here!
Here’s my amulet:
((circle(10) fillColor Color.black) on
(circle(20) fillColor Color.cornflowerBlue) on
(circle(30) fillColor Color.white) on
(circle(50) fillColor Color.darkBlue))
3.4 Creating Colors
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
We’ve seen how to use predefined colors in our images. What about creating our own colors? In this section we will see how to create colors of our own, and transform existing colors into new ones.
3.4.1 RGB Colors
Computers work with colors defined by mixing together different amounts of red, green, and blue. This “RGB” model is an additive model of color. Each red, green, or blue component can have a value between zero and 255. If all three components are set to the maximum of 255 we get pure white. If all components are zero we get black.
We can create our own RGB colors using the rgb method on the Color object. This method takes three parameters: the red, green, and blue components. These are numbers between 0 and 255, called an UnsignedByte1. There is no literal expression for UnsignedByte like there is for Int, so we must convert an Int to UnsignedByte. We can do this with the uByte method. An Int can take on more values that an UnsignedByte, so if the number is too small or too large to be represented as a UnsignedByte it will be converted to the closest values is the range 0 to 255. These examples illustrate the conversion.
0.uByte
255.uByte
128.uByte
-100.uByte // Too small, is transformed to 0
1000.uByte // Too big, is transformed to 255
(Note that UnsignedByte is a feature of Doodle. It is not something provided by Scala.)
Now we know how to construct UnsignedBytes we can make RGB colors.
Color.rgb(255.uByte, 255.uByte, 255.uByte) // White
Color.rgb(0.uByte, 0.uByte, 0.uByte) // Black
Color.rgb(255.uByte, 0.uByte, 0.uByte) // Red
3.4.2 HSL Colors
The RGB color representation is not very easy to use. The hue-saturation-lightness (HSL) format more closely correponds to how we perceive color. In this representation a color consists of:
- hue, which is an angle between 0 and 360 degrees giving a rotation around the color wheel.
- saturation, which is a number between 0 and 1 giving the intensity of the color from a drab gray to a pure color; and
- lightness between 0 and 1 giving the color a brightness varying from black to pure white.
A color wheel showing changes in hue (rotations) and lightness (distance from the center) with saturation fixed at 1.
A gradient showing how changing saturation effects color, with hue and lightness held constant. Saturation is zero on the left and one on the right.
We can construct a color in the HSL representation using the Color.hsl method. This method takes as parameters the hue, saturation, and lightness. The hue is an Angle. We can convert a Double to an Angle using the degrees (or radians) methods.
0.degrees
180.degrees
3.14.radians
Saturation and lightness are both normalized to between 0.0 and 1.0. We can convert a Double to a normalized value with the .normalized method.
0.0.normalized
1.0.normalized
1.2.normalized // Too big, is clipped to 1.0
-1.0.normalized // Too small, is clipped to 0.0
We can now create colors using the HSL representation.
Color.hsl(0.degrees, 0.8.normalized, 0.6.normalized) // A pastel red
To view this color we can render it in a picture. See fig. 6 for an example.
Figure 6: Rendering pastel red in a triangle
3.4.3 Manipulating Colors
The effectiveness of a composition often depends as much on the relationships between colors as the actual colors used. Colors have several methods that allow us to create a new color from an existing one. The most commonly used ones are:
spin, which rotates the hue by anAngle;saturateanddesaturate, which respectively add and subtract aNormalisedvalue from the color; andlightenanddarken, which respecitvely add and subtract aNormalisedvalue from the lightness.
For example,
((circle(100) fillColor Color.red) beside
(circle(100) fillColor Color.red.spin(15.degrees)) beside
(circle(100) fillColor Color.red.spin(30.degrees))).lineWidth(5.0)
produces fig. 7.
Figure 7: Three circles, starting with Color.red and spinning by 15 degrees for each successive circle
Here’s a similar example, this time manipulating saturation and lightness, shown in fig. 8.
(((circle(20) fillColor (Color.red darken 0.2.normalized))
beside (circle(20) fillColor Color.red)
beside (circle(20) fillColor (Color.red lighten 0.2.normalized))) above
((rectangle(40,40) fillColor (Color.red desaturate 0.6.normalized))
beside (rectangle(40,40) fillColor (Color.red desaturate 0.3.normalized))
beside (rectangle(40,40) fillColor Color.red)))
Figure 8: The top three circles show the effect of changing lightness, and the bottom three squares show the effect of changing saturation.
3.4.4 Transparency
We can also add a degree of transparency to our colors, by adding an alpha value. An alpha value of 0.0 indicates a completely transparent color, while a color with an alpha of 1.0 is completely opaque. The methods Color.rgba and Color.hsla have a fourth parameter that is a Normalized alpha value. We can also create a new color with a different transparency by using the alpha method on a color. Here’s an example, shown in fig. 9.
((circle(40) fillColor (Color.red.alpha(0.5.normalized))) beside
(circle(40) fillColor (Color.blue.alpha(0.5.normalized))) on
(circle(40) fillColor (Color.green.alpha(0.5.normalized))))
Figure 9: Circles with alpha of 0.5 showing transparency
Exercises
Complementary Triangles
Create three triangles, arranged in a triangle, with complementary colors. Complementary colors are colors that are similar in hue. See a (fairly elaborate) example in fig. 10.
Figure 10: Complementary triangles. The colors chosen are variations on darkSlateBlue
These sort of examples are getting a bit too long to write out at the console. We’ll look at a way around this next.
((triangle(40, 40)
lineWidth 6.0
lineColor Color.darkSlateBlue
fillColor (Color.darkSlateBlue lighten 0.3.normalized saturate 0.2.normalized spin 10.degrees)) above
((triangle(40, 40)
lineWidth 6.0
lineColor (Color.darkSlateBlue spin (-30.degrees))
fillColor (Color.darkSlateBlue lighten 0.3.normalized saturate 0.2.normalized spin (-20.degrees))) beside
(triangle(40, 40)
lineWidth 6.0
lineColor (Color.darkSlateBlue spin (30.degrees))
fillColor (Color.darkSlateBlue lighten 0.3.normalized saturate 0.2.normalized spin (40.degrees)))))
3.5 Exercises
Exercise: Compilation Target
Create a line drawing of an archery target with three concentric scoring bands:
Simple archery target
For bonus credit add a stand so we can place the target on a range:
Archery target with a stand
The simplest solution is to create three concentric circles using the on operator:
(Circle(10) on Circle(20) on Circle(30)).drawFor the extra credit we can create a stand using two rectangles:
(
Circle(10) on
Circle(20) on
Circle(30) above
Rectangle(6, 20) above
Rectangle(20, 6)
).drawExercise: Stay on Target
Colour your target red and white, the stand in brown (if applicable), and some ground in green:
Colour archery target
The trick here is using parentheses to control the order of composition. The fillColor(), lineColor(), and lineWidth() methods apply to a single image—we need to make sure that image comprises the correct set of shapes:
(
( Circle(10) fillColor Color.red ) on
( Circle(20) fillColor Color.white ) on
( Circle(30) fillColor Color.red lineWidth 2 ) above
( Rectangle(6, 20) above Rectangle(20, 6) fillColor Color.brown ) above
( Rectangle(80, 25) lineWidth 0 fillColor Color.green )
).draw4 Writing Larger Programs
We’re getting to the point where it’s inconvenient to type programs into the console. In this chapter we’ll learn about two tools for writing larger programs:
- saving programs to a file so we don’t have to type code over and over again;
- giving names to values so we can reuse them.
If you run the examples from the SBT console within Doodle they will just work. If not, you will need to start your code with the following imports to make Doodle available.
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
4.1 Working Within the Console
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
Your text editor or IDE will allow you to save code to a file, but we need to save them in the right place so the Scala compiler can find them. If you’re working from the Doodle template you should save your code in the directory src/main/scala/.
How do we use code that we saved to a file from the console? There is a special command, that only works from the console, that allows us to run code saved in a file. This command is called :paste2. We follow :paste with the name of the file we want to run. For example, if we save in the file src/main/scala/Example.scala the expression
circle(100) fillColor Color.paleGoldenrod lineColor Color.indianRed
we can then run this code by writing at the console
:paste src/main/scala/Example.scala
// res0: doodle.core.Image = ContextTransform(<function1>,ContextTransform(<function1>,Circle(100.0)))Note the value has been given the name res0 in the example above. If you’re following along, the name in your console might end with a different number depending on what you’ve already typed into the console. We can draw the image by evaluating res0.draw (or the correct name for your console).
4.1.1 Tips for Using the Console
Here are a few tips for using the console more productively:
If you press the up arrow you’ll get the last thing you typed into the console. Handy to avoid having to type in those long file names over and over again! You can press up multiple times to go through the history of your interactions at the console.
You can press the
Tabkey to get the console to suggest completions for code, but unfortunately not file names, you’re typing. For example, if you typeStriand then pressTab, the console will show possible completions. TypeStrinand the console will completeStringfor you.
Once we start saving code to a file, we’ll likely find the compiler doesn’t like our code next time we start SBT. Read the next section to see how we can fix this problem.
4.2 Coding Outside the Console
The code we’ve been writing inside the console will cause problems running outside the console. For example, put the following code into Example.scala in the src/main/scala.
circle(100) fillColor Color.paleGoldenrod lineColor Color.indianRed
Now restart SBT and try to enter the console. You should see an error similar to
[error] src/main/scala/Example.scala:1: expected class or object definition
[error] circle(100) fillColor Color.paleGoldenrod lineColor Color.indianRed
[error] ^
[error] one error foundYou’ll see something similar if you’re using an IDE.
The problem is this:
- Scala is attempting to compile all our code before the console starts; and
- there are restrictions on code written in files that don’t apply to code written directly in the console.
We need to know about these restrictions and change how we write code in files accordingly.
The error message gives us some hint: expected class or object definition. We don’t yet know what a class is, but we do know about objects—all values are objects. In Scala all code in a file must be written inside an object or class. We can easily define an object by wrapping an expression like the below.
object Example {
(circle(100) fillColor Color.paleGoldenrod lineColor Color.indianRed).draw
}
Now the code won’t compile for a different reason. I get a lot of errors similar to
[error] doodle/shared/src/main/scala/doodle/examples/Example.scala:2: not found: value circle
[error] (circle(100) fillColor Color.paleGoldenrod lineColor Color.indianRed).draw
[error] ^The compiler is saying that we’ve used a name, circle, but the compiler doesn’t know what value this name refers to. It will have a similiar issue with Color in the code above. We’ll talk in more details about names in just a moment. Right now let’s tell the compiler where it can find the values for these names by adding some import statements. The name Color is found inside a package called doodle.core, and the name circle is within the object Image that is in doodle.core. We can tell the compiler to use all the name in doodle.core, and all the names in the the object Image by writing
import doodle.core._
import doodle.core.Image._
There are a few other names that the compiler will need to find for the complete code to work. We can import these with the lines
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
We should place all these imports at the top of the file, so the complete code looks like
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
object Example {
(circle(100) fillColor Color.paleGoldenrod lineColor Color.indianRed).draw
}
With this in place the code should compile without issue.
Now when we go to the console within SBT we can refer to our code using the name, Example, that we’ve given it.
Example // draws the imageExercise
If you haven’t done so already, save the code above in the file src/main/scala/Example.scala and check that the code compiles and you can access it from the console.
Introduce names, val, and imports.
5 The Substitution Model of Evaluation
6 Methods
7 Structural Recursion
In this chapter we see our first major pattern for structuring computations: structural recursion over the natural numbers. That’s quite a mouthful, so let’s break it down:
By a pattern, we mean a way of writing code that is useful in lots of different contexts. We’ll encounter structural recursion in many different situations throughout this book.
By the natural numbers we mean the whole numbers 0, 1, 2, and upwards.
By recursion we mean something that refers to itself. Structural recursion means a recursion that follows the structure of the data it is processing. If the data is recursive (refers to itself) then the structural recursion will also refer to itself. We’ll see in more detail what this means in a moment.
If you run the examples from the SBT console within Doodle they will just work. If not, you will need to start your code with the following imports to make Doodle available.
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
7.1 A Line of Boxes
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
Let’s start with an example, drawing a line or row of boxes as in fig. 11.
Figure 11: Six boxes filled with Royal Blue
Let’s define a box to begin with.
val aBox = Image.rectangle(20, 20).fillColor(Color.royalBlue)
Then one box in a row is just
val oneBox = aBox
If we want to have two boxes side by side, that is easy enough.
val twoBoxes = aBox beside oneBox
Similarly for three.
val threeBoxes = aBox beside twoBoxes
And so on for as many boxes as we care to create.
You might think this is an unusual way to create these images. Why not just write
val threeBoxes = aBox beside aBox beside aBox
for example? These two definitions are equivalent. We’ve chosen to write later images in terms of earlier ones to emphasise the structure we’re dealing with, which is building up to structural recursion.
Writing images in this way could get very tedious. What we’d really like is some way to tell the computer the number of boxes we’d like. More technically, we would like to abstract over the expressions above. We learned in the previous chapter that methods abstract over expressions, so let’s try to write a method to solve this problem.
We’ll start by writing a method skeleton that defines, as usual, what goes into the method and what it evaluates to. In this case we supply an Int count, which is the number of boxes we want, and we get back an Image.
def boxes(count: Int): Image =
???
Now comes the new part, the strucural recursion. We noticed that threeBoxes above is defined in terms of twoBoxes, and twoBoxes is itself defined in terms of box. We could even define box in terms of no boxes, like so:
val oneBox = aBox beside Image.empty
Here we used Image.empty to represent no boxes.
Imagine we had already implemented the boxes method. We can say the following properties of boxes always hold, if it is correctly implemented:
boxes(0) == Image.emptyboxes(1) == aBox beside boxes(0)boxes(2) == aBox beside boxes(1)boxes(3) == aBox beside boxes(2)
The last three properties all have the same general shape. We can describe all of them, and any case for n > 0, with the single property boxes(n) == aBox beside boxes(n - 1). So we’re left with two properties
boxes(0) == Image.emptyboxes(n) == aBox beside boxes(n-1)
These two properties completely define the behavior of boxes. In fact we can implement boxes by converting these properties into code.
A full implementation of boxes is
def boxes(count: Int): Image =
count match {
case 0 => Image.empty
case n => aBox beside boxes(n-1)
}
Try it and see what results you get! This implementation is only tiny bit more verbose than the properties we wrote above, and is our first structural recursion over the natural numbers.
At this point we have two questions to answer. Firstly, how does this match expression work? More importantly, is there some general principle we can use to create methods like this on our own? Let’s take each question in turn.
Exercise: Stacking Boxes
Even before we get into the details of match expressions you should be able to modify boxes to produce an image like fig. 12.
At this point we’re trying to get used to the syntax of match, so rather than copying and pasting boxes write it all out by hand again to get some practice.
Figure 12: Three stacked boxes filled with Royal Blue
All you to do is change beside to above in boxes.
def stackedBoxes(count: Int): Image =
count match {
case 0 => Image.empty
case n => aBox beside stackedBoxes(n-1)
}
7.2 Match Expressions
In the previous section we saw the match expression
count match {
case 0 => Image.empty
case n => aBox beside boxes(n-1)
}How are we to understand this new kind of expression, and write our own? Let’s break it down.
The very first to say is that match is indeed an expression, which means it evaluates to a value. If it didn’t, the boxes method would not work!
To understand what it evaluates to we need more detail. A match expression in general has the shape
<anExpression> match {
case <pattern1> => <expression1>
case <pattern2> => <expression2>
case <pattern3> => <expression3>
...
}<anExpression>, concretely count in the case above, is the expresssion that evaluates to the value we’re matching against. The patterns <pattern1> and so on are matched against this value. So far we’ve seen two kinds of patterns:
- a literal (as in
case 0) which matches exactly the value that literal evaluates to; and - a wildcard (as in
case n) which matches anything, and introduces a binding within the right-hand side expression.
Finally, the right-hand side expressions, <expression1> and so on, are just expresssions like any other we’ve written so far. The entire match expression evalutes to the value of the right-hand side expression of the first pattern that matches. So when we call boxes(0) both patterns will match (because the wildcard matches anything), but because the literal pattern comes first the expression Image.empty is the one that is evaluated.
A match expression that checks for all possible cases is called an exhaustive match. If we can assume that count is always greater or equal to zero, the match in boxes is exhaustive.
Once we’re comfortable with match expressions we need to look at the structure of the natural numbers before we can explain structural recursion over them.
Exercises
Guess the Result
Let’s check our understanding of match by guessing what each of the following expressions evaluates to, and why.
"abcd" match {
case "bcde" => 0
case "cdef" => 1
case "abcd" => 2
}
1 match {
case 0 => "zero"
case 1 => "one"
case 1 => "two"
}
1 match {
case n => n + 1
case 1 => 1000
}
1 match {
case a => a
case b => b + 1
case c => c * 2
}
The first example evalutes to 2, as the pattern "abcd" is the only match for the literal "abcd" amongst the patterns.
The second example evaluates to "one", because the first matching case is the one that is evaluated.
The third example evaluates to 2, because case n defines a wildcard pattern that matches anything.
The final example evaluates to 1 because the first matching case is evaluated.
No Match
What happens if no pattern matches in a match expression? Take a guess, than right a match expression that fails to match and see if you managed to guess correctly. (At this point we have no reason to expect any particular behavior so any reasonable guess will do.)
Here are three reasonable possibilities I can think of; perhaps you came up with something else?
- The expression could evaluate to some default, like
Image.empty(but how should Scala pick the right default?) - The Scala compiler should just not let you write code like that.
- The
matchexpression will fail at runtime.
Here’s a match expression that doesn’t match.
2 match {
case 0 => "zero"
case 1 => "one"
}
The correct answer is one of the last two possibilities, failing to compile or failing at runtime. In this example we have an error at runtime. The exact answer depends on how Scala is configured (we can tell the compiler to refuse to compile matches that it can show are not exhaustive, but this is not the default behavior).
7.3 The Natural Numbers
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
val aBox = Image.rectangle(20, 20).fillColor(Color.royalBlue)
The natural numbers are the whole numbers, or integers, greater than or equal to zero. In other words the numbers 0, 1, 2, 3, … (Some people define the natural numbers as starting at 1, not 0. It doesn’t greatly matter for our purposes which definition you choose, but here we’ll assume they start at 0.)
One interesting property of the natural numbers is that we can define them recursively. That is, we can define them in terms of themselves. This kind of circular definition seems like it would lead to nonsense. We avoid this by including in the definition a base case that ends the recursion. Concretely, the definition is:
A natural number n is
- 0; or
- 1 +
m, wheremis a natural number.
The case for 0 is the base case, whilst the other case is recursive as it defines a natural number n in terms of a natural number m. Because m is always smaller than n, and the base case is the smallest possible natural number, this definition defines all of the natural numbers.
Given a natural number, say, 3, we can break it down using the definition above as follows:
3 = 1 + 2 = 1 + (1 + 1) = 1 + (1 + (1 + 0))
We use the recursive rule to expand the equation, until we cannot use it any more. We then use the base case to stop the recursion.
7.4 Structural Recursion
Now onto structural recursion. The structural recursion pattern for the natural numbers gives us two things:
- a reusable code skeleton for processing any natural number; and
- the guarantee that we can use this skeleton to implement any computation on natural numbers.
Remember we wrote boxes as
def boxes(count: Int): Image =
count match {
case 0 => Image.empty
case n => aBox beside boxes(n-1)
}
When we developed boxes we just seemed to stumble upon this pattern. Here we see that this pattern follows directly from the definition of the natural numbers. Remember the recursive definition of the natural numbers: a natural number n is
- 0; or
- 1 +
m, wheremis a natural number.
The patterns in the match expression exactly match this definition. The expression
count match {
case 0 => ???
case n => ???
}means we’re checking count for two cases, the case when count is 0, and the case when count is any other natural number n (which is 1 + m).
The right hand side of the match expression says what we do in each case. The case for zero is Image.empty. The case for n is aBox beside boxes(n-1).
Now for the really important point. Notice that the structure of the right-hand side mirrors the structure of the natural number we match. When we match the base case 0, our result is the base case Image.empty. When we match the recursive case n the structure of the right hand side matches the structure of the recursive case in the definition of natural numbers. The definition states that n is 1 + m. On the right-hand side we replace 1 with aBox, we replace + with beside, and we recursively call boxes with m (which is n-1) where the definition recurses.
def boxes(count: Int): Image =
count match {
case 0 => Image.empty
case n => aBox beside boxes(n-1)
}
To reiterate, the left hand side of the match expression exactly matches the definition of natural numbers. The right-hand also matches the definition but we replace natural numbers with images. The image that is equivalent to zero is Image.empty. The image that is equivalent to 1 + m is aBox beside boxes(m).
This general pattern holds for anything we care to write that transforms the natural numbers into some other type. We always have a match expression. We always have the two patterns, corresponding to the base and recursive cases. The right hand side expressions always consist of the base case, and the recursive case which itself hasa result specific substitute for 1 and +, and a recursive call for n-1.
The general pattern is
def <doSomething>(count: Int): <Result> =
count match {
case 0 => <resultBase>
case n => <resultUnit> <add> <doSomething>(n-1)
}where <Result>, <resultBase>, <resultUnit>, and <add> are specific to the problem we’re solving. So to implement a structural recursion over the natural numbers we must
- recognise the method we’re writing has a natural number as it’s input;
- work out the result type; and
- decide what should be the base, unit, and addition for the result.
We’re now ready to go explore the fun that can be had with this simple but powerful tool.
7.4 Proofs and Programs
If you’ve studied maths you have probably come across proof by induction. The general pattern of a proof by induction looks very much like the general pattern of a structural recursion over the natural numbers. This is no coincidence; there is a deep relationship between the two. We can view a structural recursion over the natural numbers as exactly a proof by induction. When we claim the ability to write any transformation on the natural numbers in terms of the structural recursion skeleton, this claim is backed up by the mathematical foundation we’re implicitly using. We can also prove properties of our code by using the connection between the two: any structural recursion is implicitly defining a proof of some property.
This general connection between proofs and programs is known as the Howard-Curry Isomorphism.
Exercises
Cross
Our first exercise is to create a method cross that will generate cross images. fig. 13 shows four cross images, which correspond to calling the method cross with 0 to 3.
The method skeleton is
def cross(count: Int): Image =
???
Figure 13: Crosses generated by count from 0 to 3.
What pattern will we use to fill in the body of cross? Write out the pattern.
It’s structural recursion over the natural numbers. You should end up with something like
def cross(count: Int): Image =
count match {
case 0 => <resultBase>
case n => <resultUnit> <add> cross(n-1)
}Now we’ve identified the pattern we’re using, we need to fill in the problem specific parts:
- the base case; and
- the unit and addition operators.
Hint: use fig. 13 to identify the elements above.
From the picture we can work out that the base case is a circle.
Successive elements in the picture add circles to the top, bottom, left, and right of the image. So our unit is the same as the base, a circle, but the addition operator is not a simple beside or above like we’ve seen before but unit beside (unit above cross(n-1) above unit) beside unit.
Now finish the implementation of cross.
Here’s what we wrote.
def cross(count: Int): Image = {
val unit = Image.circle(20)
count match {
case 0 => unit
case n => unit beside (unit above cross(n-1) above unit) beside unit
}
}Chessboard
We saw in the cross exercise that the hard part was identifying the recursive structure in what we were trying to create. Once we’d done that filling in the structural recursion pattern was straightforward.
In this exercise and the next we’re trying to sharpen you eye for recursive structure. Your mission in this exercise to identify the recursive structure in a chessboard, and implement a method to draw chessboards. The method skeleton isn’t
def chessboard(count: Int): Image =
???
In fig. 14 we have example chessboards drawn with count ranging from 0 to 2. Hint: note that now count does not give us the width of the chessboard, but tells us the number of atomic “chessboard units” we combine.
Figure 14: Chessboards generated by count from 0 to 2.
Implement chessboard.
chessboard is a structural recursion over the natural numbers, so right away we can write down the skeleton for this pattern.
def chessboard(count: Int): Image =
count match {
case 0 => <resultBase>
case n => <resultUnit> <add> cross(n-1)
}As before we must decide on the base, unit, and addition for the result. We’ve given you a hint by showing the progression of chessboards in fig. 14. From this we can see that the base is a two-by-two chessboard.
val blackSquare = Image.rectangle(30, 30) fillColor Color.black
val redSquare = Image.rectangle(30, 30) fillColor Color.red
val base =
(redSquare beside blackSquare) above (blackSquare beside redSquare)
Now to work out the unit and addition. Here we see a change from previous examples. The unit is the value we get from the recursive call chessboard(n-1). The addition operation is (unit beside unit) above (unit beside unit).
Putting it all together we get
def chessboard(count: Int): Image = {
val blackSquare = Image.rectangle(30, 30) fillColor Color.black
val redSquare = Image.rectangle(30, 30) fillColor Color.red
val base =
(redSquare beside blackSquare) above (blackSquare beside redSquare)
count match {
case 0 => base
case n =>
val unit = cross(n-1)
(unit beside unit) above (unit beside unit)
}
}
If you have prior programming experience you might have immediately thought of creating a chessboard via two nested loops. Here we’re taking a different approach by defining a larger chessboard as a composition of smaller chessboards. Grasping this different approach to decomposing problems is a key step in becoming proficient in functional programming.
Sierpinkski Triangle
The Sierpinski triangle, show in fig. 15, is a famous fractal. (Technically, fig. 15 shows a Sierpinkski triangle.)
Figure 15: The Sierpinski triangle.
Although it looks complicated we can break the structure down into a form that we can generate with structural recursion over the natural numbers. Implement a method with skeleton
def sierpinski(count: Int): Image =
???
No hints this time. We’ve already seen everything we need to know.
The key step is to recognise that the basic unit of the Sierpinski triangle is triangle above (triangle beside triangle). Once we’ve worked this out, the code has exactly the same structure as chessboard. Here’s our implementation.
def sierpinski(count: Int): Image = {
val triangle = Image.triangle(10, 10) lineColor Color.magenta
count match {
case 0 => triangle above (triangle beside triangle)
case n =>
val unit = sierpinski(n-1)
unit above (unit beside unit)
}
}
7.5 Reasoning about Recursion
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
We’re now experienced users of structural recursion over the natural numbers. Let’s now return to our substitution model and see if it works with our new tool of recursion.
Recall that substution say we can substitute the value of an expression wherever we see a value. In the case of a method call, we can substitute the body of the method with appropriate renaming of the parameters.
Our very first example of recursion was boxes, written like so:
val aBox = Image.rectangle(20, 20).fillColor(Color.royalBlue)
def boxes(count: Int): Image =
count match {
case 0 => Image.empty
case n => aBox beside boxes(n-1)
}
Let’s try using substitution on boxes(3) to see what we get.
Our first substitution is
boxes(3)
// Substitute body of `boxes`
3 match {
case 0 => Image.empty
case n => aBox beside boxes(n-1)
}
Knowing how to evaluate a match expression and using substitution again gives us
3 match {
case 0 => Image.empty
case n => aBox beside boxes(n-1)
}
// Substitute right-hand side expression of `case n`
aBox beside boxes(2)
We can substitute again on boxes(2) to obtain
aBox beside boxes(2)
// Substitute body of boxes
aBox beside {
2 match {
case 0 => Image.empty
case n => aBox beside boxes(n-1)
}
}
// Substitute right-hand side expression of `case n`
aBox beside {
aBox beside boxes(1)
}
Repeating the process a few more times we get
aBox beside {
aBox beside {
1 match {
case 0 => Image.empty
case n => aBox beside boxes(n-1)
}
}
}
// Substitute right-hand side expression of `case n`
aBox beside {
aBox beside {
aBox beside boxes(0)
}
}
// Substitute body of boxes
aBox beside {
aBox beside {
aBox beside {
0 match {
case 0 => Image.empty
case n => aBox beside boxes(n-1)
}
}
}
}
// Substitute right-hand side expression of `case 0`
aBox beside {
aBox beside {
aBox beside {
Image.empty
}
}
}
Our final result, which simplies to
aBox beside aBox beside aBox beside Image.empty
is exactly what we expect. Therefore we can say that substitution works to reason about recursion. This is great! However the substitutions are quite complex and difficult to keep track of without writing them down. A more practical way to reason about recursion is to assume that the recursion works and only worry about what new comes from each step.
For example, when reasoning about boxes
def boxes(count: Int): Image =
count match {
case 0 => Image.empty
case n => aBox beside boxes(n-1)
}
we can tell the base case is correct by inspection. Looking at the recursive case we assume that boxes(n-1) will do the right thing. We then ask ourselves “is what we do in the recursion case correct is the recursion itself is correct?” The answer is yes: if the recursion boxes(n-1) creates n-1 boxes in a line, sticking a box in front of them is the right thing to do. This way of reasoning is much more compact that using substitution and guaranteed to work if we’re using structural recursion.
Exercises
Below are some rather silly examples of structural recursion. Work out if the methods do what they claim to do without running them.
// Given a natural number, returns that number
// Examples:
// identity(0) == 0
// identity(3) == 3
def identity(n: Int): Int =
n match {
case 0 => 0
case n => 1 + identity(n-1)
}
It sure does! The base case is straightforward. Looking at the recursive case, we assume that identity(n-1) returns the identity for n-1 (which is exactly n-1). The identity for n is then 1 + identity(n-1).
// Given a natural number, double that number
// Examples:
// double(0) == 0
// double(3) == 6
def double(n: Int): Int =
n match {
case 0 => 0
case n => 2 * double(n-1)
}
No way! This method is broken in two different ways. Firstly, because we’re multiplying in the recursive case we will eventualy end up multiplying by base case of zero, and therefore the entire result will be zero.
We might try and fix this by adding a case for 1 (and perhaps wonder why the structural recursion skeleton let us down).
def double(n: Int): Int =
n match {
case 0 => 0
case 1 => 1
case n => 2 * double(n-1)
}
This doesn’t give us the correct result, however! We’re doing the wrong thing at the recursive case: we should be adding, not multiplying.
A bit of algebra:
2(n-1 + 1) == 2(n-1) + 2So if double(n-1) is 2(n-1) then we should add 2, not multiply by 2. The correct method is
def double(n: Int): Int =
n match {
case 0 => 0
case n => 2 + double(n-1)
}
7.6 Auxillary Parameters
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
val aBox = Image.rectangle(20, 20).fillColor(Color.royalBlue)
We’ve seen how to use structural recursion over the natural numbers to write a number of interesting programs. In this section we’re going to see an extension that allows us to write more complex programs using auxillary parameters. An auxillary parameter is just an additional parameter to our method that allows us to pass extra information down the recursive call.
For example, imagine creating the picture in fig. 16, which shows a line of boxes that grow in size as we move along the line.
Figure 16: Boxes that grow in size with each recursion.
How can we create this image?
We know it has to be a structural recursion over the natural numbers, so we can immediately write down the skeleton
def growingBoxes(count: Int): Image =
count match {
case 0 => base
case n => unit add growingBoxes(n-1)
}Using what we learned working with boxes earlier we can go a bit further and write down
def growingBoxes(count: Int): Image =
count match {
case 0 => Image.empty
case n => Image.rectangle(???,???) beside growingBoxes(n-1)
}The challenge becomes how to make the box grow in size as we move to the right.
There are two ways to do this. The tricky way is to switch the order in the recursive case and make the size of the box a function of n. Here’s the code.
def growingBoxes(count: Int): Image =
count match {
case 0 => Image.empty
case n => growingBoxes(n-1) beside Image.rectangle(n*10, n*10)
}
Spend some time figuring out why this works before moving on to the solution using an auxillary parameter.
Using an auxillary parameter we simply add another parameter to growingBoxes that tells us how big the current box should be. When we recurse we change this size. Here’s the code.
def growingBoxes(count: Int, size: Int): Image =
count match {
case 0 => Image.empty
case n => Image.rectangle(size, size) beside growingBoxes(n-1, size + 10)
}
The auxillary parameter method has two advantages: we only have to think about what changes from one recursion to the next (in this case, the box gets larger), and it allows the caller to change this parameter (for example, making the starting box larger or smaller).
Now we’ve seen the auxillary parameter method let’s practice using it.
Gradient Boxes
In this exercise we’re going to draw a picture like that in fig. 17. We already know how to draw a line of boxes. The challenge in this exercise is to make the color change at each step.
Hint: you can spin the fill color at each recursion.
Figure 17: Five boxes filled with changing colors starting from Royal Blue
There are two ways to implement a solution. The auxillary parameter method is to add an extra parameter to gradientBoxes and pass the Color through the structural recursion.
def gradientBoxes(n: Int, color: Color): Image =
n match {
case 0 => Image.empty
case n => aBox.fillColor(color) beside gradientBoxes(n-1, color.spin(15.degrees))
}
We could also make the fill color a function n, as we demonstrated with the box size in growingBoxes above.
def gradientBoxes(n: Int): Image =
n match {
case 0 => Image.empty
case n => aBox.fillColor(Color.royalBlue.spin((15*n).degrees)) beside gradientBoxes(n-1)
}
Concentric Circles
Now let’s try a variation on the theme, drawing concentric circles as shown in fig. 18. Here we are changing the size rather than the color of the image at each step. Otherwise the pattern stays the same. Have a go at implementing it.
Figure 18: Concentric circles, colored Royal Blue
This is almost identical to growingBoxes.
def concentricCircles(count: Int, size: Int): Image =
count match {
case 0 => Image.empty
case n => Image.circle(size) on concentricCircles(n-1, size + 5)
}
Once More, With Feeling
Now let’s combine both techniques to change size and color on each step, giving results like those shown in fig. 19. Experiment until you find something you like.
Figure 19: Concentric circles with interesting color variations
Here’s our solution, where we’ve tried to break the problem into reusable parts and reduce the amount of repeated code. We still have a lot of repetition as we don’t yet have the tools to get rid of more. We’ll come to that soon.
def circle(size: Int, color: Color): Image =
Image.circle(size).lineWidth(3.0).lineColor(color)
def fadeCircles(n: Int, size: Int, color: Color): Image =
n match {
case 0 => Image.empty
case n => circle(size, color) on fadeCircles(n-1, size+7, color.fadeOutBy(0.05.normalized))
}
def gradientCircles(n: Int, size: Int, color: Color): Image =
n match {
case 0 => Image.empty
case n => circle(size, color) on gradientCircles(n-1, size+7, color.spin(15.degrees))
}
def image: Image =
fadeCircles(20, 50, Color.red) beside gradientCircles(20, 50, Color.royalBlue)
7.7 Nested Methods
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
A method is a declaration. The body of a method can contain declarations and expressions. Therefore, a method declaration can contiain other method declarations.
To see why this is useful, lets look at a method we wrote earlier:
def cross(count: Int): Image = {
val unit = Image.circle(20)
count match {
case 0 => unit
case n => unit beside (unit above cross(n-1) above unit) beside unit
}
}
We have declared unit inside the method cross. This means the declaration of unit is only in scope within the body of cross. It is good practice to limit the scope of declarations to the minimum needed, to avoid accidentally shadowing othering declarations. However, let’s consider the runtime behavior of cross and we’ll see that is has some undesireable characteristics.
We’ll use our substitution model to expand cross(1).
cross(1)
// Expands to
{
val unit = Image.circle(20)
1 match {
case 0 => unit
case n => unit beside (unit above cross(n-1) above unit) beside unit
}
}
// Expands to
{
val unit = Image.circle(20)
unit beside (unit above cross(0) above unit) beside unit
}
// Expands to
{
val unit = Image.circle(20)
unit beside (unit above
{
val unit = Image.circle(20)
0 match {
case 0 => unit
case n => unit beside (unit above cross(n-1) above unit) beside unit
}
}
above unit) beside unit
}
// Expands to
{
val unit = Image.circle(20)
unit beside (unit above
{
val unit = Image.circle(20)
unit
}
above unit) beside unit
}The point of this enormous expansion is to demonstrate that we’re recreating unit every time we recurse within cross. We can prove this is true by printing something every time unit is created.
def cross(count: Int): Image = {
val unit = {
println("Creating unit")
Image.circle(20)
}
count match {
case 0 => unit
case n => unit beside (unit above cross(n-1) above unit) beside unit
}
}
cross(1)
This doesn’t matter greatly for unit because it’s very small, but we could be doing that takes up a lot of memory or time, and it’s undesireable to repeat it when we don’t have to.
We could solve this by shifting unit outside of cross.
val unit = {
println("Creating unit")
Image.circle(20)
}
def cross(count: Int): Image = {
count match {
case 0 => unit
case n => unit beside (unit above cross(n-1) above unit) beside unit
}
}
cross(1)
This is undesirable because unit now has a larger scope than needed. A better solution it to use a nested or internal method.
def cross(count: Int): Image = {
val unit = {
println("Creating unit")
Image.circle(20)
}
def loop(count: Int): Image = {
count match {
case 0 => unit
case n => unit beside (unit above loop(n-1) above unit) beside unit
}
}
loop(count)
}
cross(1)
This has the behavior we’re after, creating unit only once while minimising its scope. The internal method loop is using structural recursion exactly as before. We just need to ensure that we call it in cross. I usually name this sort of internal method loop or iter (short for iterate) to indicate that they’re performing a loop.
This technique is just a small variation of what we’ve done already, but let’s do a few exercises to make sure we’ve got the pattern.
Exercises
Chessboard
Rewrite chessboard using a nested method so that blackSquare, redSquare, and base are only created once when chessboard is called.
def chessboard(count: Int): Image = {
val blackSquare = Image.rectangle(30, 30) fillColor Color.black
val redSquare = Image.rectangle(30, 30) fillColor Color.red
val base =
(redSquare beside blackSquare) above (blackSquare beside redSquare)
count match {
case 0 => base
case n =>
val unit = cross(n-1)
(unit beside unit) above (unit beside unit)
}
}
Here’s how we did it. It has exactly the same pattern we used with boxes.
def chessboard(count: Int): Image = {
val blackSquare = Image.rectangle(30, 30) fillColor Color.black
val redSquare = Image.rectangle(30, 30) fillColor Color.red
val base =
(redSquare beside blackSquare) above (blackSquare beside redSquare)
def loop(count: Int): Image =
count match {
case 0 => base
case n =>
val unit = loop(n-1)
(unit beside unit) above (unit beside unit)
}
loop(count)
}
Boxing Clever
Rewrite boxes, shown below, so that aBox is only in scope within boxes and only created once when boxes is called.
val aBox = Image.rectangle(20, 20).fillColor(Color.royalBlue)
def boxes(count: Int): Image =
count match {
case 0 => Image.empty
case n => aBox beside boxes(n-1)
}
We can do this in two stages, first moving aBox within boxes.
def boxes(count: Int): Image = {
val aBox = Image.rectangle(20, 20).fillColor(Color.royalBlue)
count match {
case 0 => Image.empty
case n => aBox beside boxes(n-1)
}
}
Then we can use an internal method to avoid recreating aBox on every recursion.
def boxes(count: Int): Image = {
val aBox = Image.rectangle(20, 20).fillColor(Color.royalBlue)
def loop(count: Int): Image =
count match {
case 0 => Image.empty
case n => aBox beside loop(n-1)
}
loop(count)
}
7.8 Conclusions
In this chapter we’ve seen our first big pattern for structuring code, structural recursion over the natural numbers. We’ve seen a lot of examples that generate images, but we can use this pattern for anything that is transforming a natural number into anything else (including other natural numbers).
We’ll use this pattern, and other variants of structural recursion, throughout the book.
8 Horticulture and Higher-order Functions
In this chapter we’re going to learn how to draw flowers and to use functions as first-class values. A first-class value is something we can pass as a parameter to a method or return as a result from a method call. If we pass a function as an argument to another function then:
- the function that is passed is being used as a first-class value; and
- the function that is receiving the function parameter is a called a higher-order function.
This terminology is not especially important, but you’ll encounter it in other writing so it’s important to know (at least vaguely) what it means. It will soon become clearer when we see some examples.
So far we have used the terms function and method interchangably. We’ll soon see that in Scala these two terms have distinct, though related, meanings.
Enough background. Let’s dive in to see:
- how we create functions in Scala; and
- how we use first-class functions to structure programs.
Our motivating example for this will be drawing flowers as in fig. 20.
Figure 20: A flower created using the techniques in this chapter
If you run the examples from the SBT console within Doodle they will just work. If not, you will need to start your code with the following imports to make Doodle available.
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
8.1 Parametric Curves
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
We’ll start by drawing a circle. We already know how to do this. Just write circle(10).draw, for example. Instead of using the built-in method, however, let’s plot points on a circle ourselves. This will give us the control we need to change the change the shape of the circle, producing a flower shape.
We can define a circle using what’s called a parametric equation. This is a fancy term for a function that takes some input (the parameter in parametric) and returns an x and y coordinate.
In Doodle we have a Point type to represent a position in two dimensions. We have two equivalent representations in terms of:
- x and y coordinates, called a cartesian representation; and
- in terms of an angle and distance at that angle from the origin (the radius), called a polar representation.
We can create points in the carteisan representation using Point.cartesian, and in the polar representation using Point.polar. The table below shows the main methods on Point.
| Operator | Type | Description | Example |
|---|---|---|---|
Point.cartesian(Double, Double) |
Point |
Constructs a Point using the cartesian representation. |
Point.cartesian(1.0, 1.0) |
Point.polar(Double, Angle) |
Point |
Constructs a Point using the polar representation. |
Point.polar(1.0, 90.degrees) |
Point.zero |
Point |
Constructs a Point at the origin (x and y are zero) |
Point.zero |
Point.x |
Double |
Gets the x coordinate of the Point. |
Point.zero.x |
Point.y |
Double |
Gets the y coordinate of the Point. |
Point.zero.y |
Point.r |
Double |
Gets the radius of the Point. |
Point.zero.r |
Point.angle |
Angle |
Gets the angle of the Point. |
Point.zero.angle |
For our input we’ll take an Angle, which tells us where on the circle we are. So for us, our parametric equations will be methods or functions from Angle to Point. A bit of geometry shows us that given an angle angle and x and y coordinates should be cos(angle) and sin(angle) respectively. We can define the parametric equation for a circle like so:
def parametricCircle(angle: Angle): Point =
Point.cartesian(angle.cos, angle.sin)
Now we could sample a point on the circle every, say, 1 degree, giving us some fairly closely spaced points around the perimeter of the circle. To create an image we can draw something at each point (say, a triangle). We haven’t yet seen how to do this in Doodle. We can use the at method to put an Image as a specific point relative. This method takes a vector, with type Vec. We can convert a Point to a Vec using the toVec method3. Here’s the code.
def sample(start: Angle, increment: Angle): Image = {
if(start > Angle.one) // Angle.one is one complete turn. I.e. 360 degrees
Image.empty
else
triangle(10, 10) at (parametricCircle(start).toVec) on sample(start+increment, increment)
}
This is a structural recursion, which is hopefully a familiar pattern by now.
If we draw this we’ll see a whole lot of triangles on top of each other—the circle we define with parametricCircle only has a radius of one! We need to make the circle a bit bigger. Let’s make the circle have a radius of 100 units.
def sample(start: Angle, increment: Angle): Image = {
if(start > Angle.one) { // Angle.one is one complete turn. I.e. 360 degrees
Image.empty
} else {
val pt = parametricCircle(start)
triangle(10, 10) at (Point.polar(pt.r * 100, pt.angle).toVec) on sample(start+increment, increment)
}
}
See fig. 21, which shows the result of sample(0.degrees, 5.degrees).
Figure 21: Triangles arranged in a circle, using the code from sample above.
8.1.1 Flowers
The next step to creating a flower is to using a more interesting shape than a circle. That means changing parametricCircle for a more interesting equation. Perhaps rose below.
// Parametric equation for rose with k = 7
def rose(angle: Angle) =
Point.cartesian((angle * 7).cos * angle.cos, (angle * 7).cos * angle.sin)
We can change sample to call rose instead of parametricCircle, but this is a bit unsatisfactory. What if we want to experiment with different parametric equations? It would be nice if we could pass to sample the method that creates points (i.e. the parametric equation). Can we do this? To do so we need to answer at least:
- how do we write down the type of a method as a method parameter?
- how do we differentiate between calling a method (e.g.
rose(0.degress)) and referring to the method itself.
Let’s look at the second problem. If we try referring to a method without calling it we get an error.
rose
The error message handily tells us what we need to do, and this is a good point to finally introduce functions.
8.2 Functions
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
As the error message above suggests, we can convert any method to a function using the _ operator and call it with the same parameters.
// Parametric equation for rose with k = 7
def rose(angle: Angle) =
Point.cartesian((angle * 7).cos * angle.cos, (angle * 7).cos * angle.sin)
rose _
(rose _)(0.degrees)
A function is basically a method, but we can use a function as a first-class value:
- we can pass it as an argument to a method or function;
- we can return it from a method or function; and
- we can give it a name using
val.
val roseFn = rose _
roseFn(0.degrees)
8.2.1 Function Types
To pass functions to methods we need to know how to write down their types (because when we declare a parameter we have to declare its type).
We write a function type like (A, B) => C where A and B are the types of the parameters and C is the result type. The same pattern generalises from functions of no arguments to an arbitrary number of arguments.
In our example above we want f to be a function that accepts two Ints as parameters and returns an Int. Thus we can write it as (Int, Int) => Int.
Function Type Declaration Syntax
To declare a function type, write
(A, B, ...) => Cwhere
A, B, ...are the types of the input parameters; andCis the type of the result.
If a function only has one parameter the parentheses may be dropped:
A => B8.2.2 Function Literals
There is a literal syntax for functions. For example, here is a function that adds 42 to its input.
(x: Int) => x + 42
We can apply the function to an argument in the usual way.
val add42 = (x: Int) => x + 42
add42(0)
Function Literal Syntax
The syntax for declaring a function literal is
(parameter: type, ...) => expressionwhere - the optional parameters are the names given to the function parameters; - the types are the types of the function parameters; and - the expression determines the result of the function.
8.2.3 Functions as Objects
Because Scala is an object oriented language, all first class values are objects. This means functions can have methods, including some useful means for composition:
val addTen = (a: Int) => a + 10
val double = (a: Int) => a * 2
val combined = addTen andThen double // this composes the two functions
combined(5)
Exercises
Function Types
What is the type of the function roseFn defined above? What does this type mean?
The type is Angle => Point. This means roseFn is a function that takes of single argument of type Angle and returns a value of type Point. In other words, roseFn transforms an Angle to a Point.
Function Literals
Write roseFn as a function literal.
val roseFn = (angle: Angle) =>
Point.cartesian((angle * 7).cos * angle.cos, (angle * 7).cos * angle.sin)
8.3 Higher Order Methods and Functions
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
Why are functions useful? We can already use methods to package up and name reusable fragments of code. What other advantages do we get from treating code as values? We’ve said we can
- pass functions as parameters to other functions and methods; and
- create methods that return functions as their results
but we haven’t used this ability yet. Let’s do that now.
Let’s consider the pattern from the concentric circles exercise as an example:
def singleShape: Image = ???
def manyShapes(n: Int): Image =
if(n == 1) {
singleShape
} else {
singleShape on manyShapes(n - 1)
}
This pattern allows us to create many different images by changing the definition of singleShape. However, each time we provide a new definition of singleShape, we also need a new definition of manyShapes to go with it.
We can make manyShapes completely general by supplying singleShape as a parameter:
def manyShapes(n: Int, singleShape: Int => Image): Image =
if(n == 1) {
singleShape(n)
} else {
singleShape(n) on manyShapes(n - 1, singleShape)
}
Now we can re-use the same definition of manyShapes to produce plain circles, circles of different hue, circles with different opacity, and so on. All we have to do is pass in a suitable definition of singleShape:
// Passing a function literal directly:
val blackCircles: Image =
manyShapes(10, (n: Int) => Circle(50 + 5*n))
// Converting a method to a function:
def redCircle(n: Int): Image =
Circle(50 + 5*n) lineColor Color.red
val redCircles: Image =
manyShapes(10, redCircle _)
Exercises
The Colour and the Shape
Starting with the code below, write color and shape functions to produce the image shown in fig. 22.
Figure 22: Colours and Shapes
def manyShapes(n: Int, singleShape: Int => Image): Image =
if(n == 1) {
singleShape(n)
} else {
singleShape(n) on manyShapes(n - 1, singleShape)
}
The manyShapes method is equivalent to the concentricCircles method from previous exercises. The main difference is that we pass in the definition of singleShape as a parameter.
Let’s think about the problem a little. We need to do two things:
write an appropriate definition of
singleShapefor each of the three shapes in the target image; andcall
manyShapesthree times, passing in the appropriate definition ofsingleShapeeach time and putting the resultsbesideone another.
Let’s look at the definition of the singleShape parameter in more detail. The type of the parameter is Int => Image, which means a function that accepts an Int parameter and returns an Image. We can declare a method of this type as follows:
def outlinedCircle(n: Int) =
Circle(n * 10)
We can convert this method to a function, and pass it to manyShapes to create an image of concentric black outlined circles:
manyShapes(10, outlinedCircle _)
This produces the output shown in fig. 23.
Figure 23: Many outlined circles
The rest of the exercise is just a matter of copying, renaming, and customising this function to produce the desired combinations of colours and shapes:
def circleOrSquare(n: Int) =
if(n % 2 == 0) Rectangle(n*20, n*20) else Circle(n*10)
(manyShapes(10, outlinedCircle) beside manyShapes(10, circleOrSquare))
See fig. 24 for the output.
Figure 24: Many outlined circles beside many circles and squares
For extra credit, when you’ve written your code to create the sample shapes above, refactor it so you have two sets of base functions—one to produce colours and one to produce shapes. Combine these functions using a combinator as follows, and use the result of the combinator as an argument to manyShapes
def colored(shape: Int => Image, color: Int => Color): Int => Image =
(n: Int) => ???
The simplest solution is to define three singleShapes as follows:
def manyShapes(n: Int, singleShape: Int => Image): Image =
if(n == 1) {
singleShape(n)
} else {
singleShape(n) on manyShapes(n - 1, singleShape)
}
def rainbowCircle(n: Int) = {
val color = Color.blue desaturate 0.5.normalized spin (n * 30).degrees
val shape = Circle(50 + n*12)
shape lineWidth 10 lineColor color
}
def fadingTriangle(n: Int) = {
val color = Color.blue fadeOut (1 - n / 20.0).normalized
val shape = Triangle(100 + n*24, 100 + n*24)
shape lineWidth 10 lineColor color
}
def rainbowSquare(n: Int) = {
val color = Color.blue desaturate 0.5.normalized spin (n * 30).degrees
val shape = Rectangle(100 + n*24, 100 + n*24)
shape lineWidth 10 lineColor color
}
val answer =
(manyShapes(10, rainbowCircle) beside
manyShapes(10, fadingTriangle) beside
manyShapes(10, rainbowSquare))
However, there is some redundancy here: rainbowCircle and rainbowTriangle, in particular, use the same definition of color. There are also repeated calls to lineWidth(10) and lineColor(color) that can be eliminated. The extra credit solution factors these out into their own functions and combines them with the colored combinator:
def manyShapes(n: Int, singleShape: Int => Image): Image =
if(n == 1) {
singleShape(n)
} else {
singleShape(n) on manyShapes(n - 1, singleShape)
}
def colored(shape: Int => Image, color: Int => Color): Int => Image =
(n: Int) =>
shape(n) lineWidth 10 lineColor color(n)
def fading(n: Int): Color =
Color.blue fadeOut (1 - n / 20.0).normalized
def spinning(n: Int): Color =
Color.blue desaturate 0.5.normalized spin (n * 30).degrees
def size(n: Int): Double =
50 + 12 * n
def circle(n: Int): Image =
Circle(size(n))
def square(n: Int): Image =
Rectangle(2*size(n), 2*size(n))
def triangle(n: Int): Image =
Triangle(2*size(n), 2*size(n))
val answer =
(manyShapes(10, colored(circle, spinning)) beside
manyShapes(10, colored(triangle, fading)) beside
manyShapes(10, colored(square, spinning)))
8.4 Exercises
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
Now we are chock full of knowledge about functions, we’re going to return to the problem of drawing flowers. We’ll be asking you to do more design work here than we have done previously.
Your task is to break down the task of drawing a flower into small functions that work together. Try to give yourself as much creative freedom as possible, by breaking out each individual component of the task into a function.
Try to do this now. If you run into problems look at our decomposition below.
8.4.1 Components
We’ve identified two components of drawing flowers:
- the parametric equation; and
- the structural recursion over angles.
What other components might we abstract into functions? What are their types? (This is a deliberately open ended question. Explore!)
Remember we had to scale the output of the parametric equation. We could abstract this into a function. What should the type of this function be? Perhaps the most obvious approach is to have function with type (Point, Double) => Point, where the Double parameter is the amount by which we scale the point. This is somehwat annoying to use, however. We have to continually pass around the Double, which never varies from its initial setting.
A better structure is to create a function with type Double => (Point => Point). This is a function to which we pass the scaling factor. It returns a function that transforms a Point by the given scaling factor. In this way we separate out the fixed scaling factor. The implementation could be
def scale(factor: Double): Point => Point =
(pt: Point) => {
Point.polar(pt.r * factor, pt.angle)
}
In our previous discussion we’ve said we’d like to abstract the parametric equation out from sample. This we can easily do with
def parametricCircle(angle: Angle): Point =
Point.cartesian(angle.cos, angle.sin)
def sample(start: Angle, increment: Angle, location: Angle => Point): Image = {
if(start > Angle.one) // Angle.one is one complete turn. I.e. 360 degrees
Image.empty
else
triangle(10, 10) at location(start).toVec on sample(start+increment, increment, location)
}
We might like to abstract out the choice of image primitive (triangle above). We could change location to be a funciton Angle => Image to accomplish this. We could also abstract out the entire problem specific part of the structural recursion. Where we had
def sample(start: Angle, increment: Angle): Image = {
if(start > Angle.one) // Angle.one is one complete turn. I.e. 360 degrees
Image.empty
else
triangle(10, 10) at (parametricCircle(start).toVec) on sample(start+increment, increment)
}
we could abstract out the base case (Image.empty) and the problem specific part on the recursion (triangle(10, 10) at (parametricCircle(start).toVec) on). The former would be just an Image but the latter is a function with type (Angle, Image) => Image. The final result is
def sample(start: Angle, increment: Angle, empty: Image, combine: (Angle, Image) => Image): Image = {
if(start > Angle.one) // Angle.one is one complete turn. I.e. 360 degrees
empty
else
combine(start, sample(start+increment, increment, empty, combine))
}
This is a very abstract function. We don’t expect most people will see this abstraction, but if you’re interested in exploring this idea more you might like to read about folds and monoids.
8.4.2 Combine
Now we’ve broken out the components we can combine them to create interesting results. Do this now.
You might end up with something like.
def parametricCircle(angle: Angle): Point =
Point.cartesian(angle.cos, angle.sin)
def rose(angle: Angle): Point =
Point.cartesian((angle * 7).cos * angle.cos, (angle * 7).cos * angle.sin)
def scale(factor: Double): Point => Point =
(pt: Point) => {
Point.polar(pt.r * factor, pt.angle)
}
def sample(start: Angle, increment: Angle, location: Angle => Point): Image = {
if(start > Angle.one) // Angle.one is one complete turn. I.e. 360 degrees
Image.empty
else
triangle(10, 10) at location(start).toVec on sample(start+increment, increment, location)
}
def locate(scale: Point => Point, point: Angle => Point): Angle => Point =
(angle: Angle) => scale(point(angle))
// Rose on circle
val flower = {
sample(0.degrees, 5.degrees, locate(scale(200), rose _)) on
sample(0.degrees, 5.degrees, locate(scale(150), parametricCircle _))
}
8.4.3 Experiment
Now experiment with the creative possibilities open to you!
Our implementation used to create fig. 20 is at Flowers.scala. What did you come up with? Let us know! Our email addresses are noel@underscore.io and dave@underscore.io.
9 Shapes, Sequences, and Stars
In this chapter we will learn how to build our own shapes out of the primitve lines and curves that make up the triangles, rectangles, and circles we’ve used so far. In doing so we’ll learn how to represent sequences of data, and manipulate such sequences using higher-order functions that abstract over structural recursion. That’s quite a lot of jargon, but we hope you’ll see it’s not as difficult as it sounds!
If you run the examples from the SBT console within Doodle they will just work. If not, you will need to start your code with the following imports to make Doodle available.
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
9.1 Paths
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
All shapes in Doodle are ultimately represented as paths. You can think of a path as giving a sequence of movements for an imaginary pen, starting from the origin. Pen movements come in three varieties:
moving the pen to a point without drawing a line;
drawing a straight line from the current position to a point; and
drawing a Bezier curve from the current position to a point, with the shape of the curve determined by two control points.
Paths themselves come in two varieties:
- open paths, where the end of the path is not necessarily the starting point; and
- closed paths, that end where they begin—and if the path doesn’t end where it started a line will be inserted to make it so.
The picture in fig. 25 illustrates the components that can make up a path, and shows the difference between open and closed paths.
Figure 25: The same paths draw as open (top) and closed (bottom) paths. Notice how the open triangle is not properly joined at the bottom left, and the closed curve inserts a straight line to close the shape.
9.1.1 Creating Paths
Now we know about paths, how do we create them in Doodle? Here’s the code that created fig. ??.
import doodle.core.Point._
val triangle =
List(
LineTo(cartesian(50, 100)),
LineTo(cartesian(100, 0)),
LineTo(cartesian(0, 0))
)
val curve =
List(BezierCurveTo(cartesian(50, 100), cartesian(100, 100), cartesian(150, 0)))
def style(image: Image): Image =
image.
lineWidth(6.0).
lineColor(Color.royalBlue).
fillColor(Color.skyBlue)
val openPaths =
style(openPath(triangle) beside openPath(curve))
val closedPaths =
style(closedPath(triangle) beside closedPath(curve))
val paths = openPaths above closedPaths
From this code we can see we create paths using the openPath and closePath methods on Image, just we create other shapes. A paths is created from a List of PathElement. The different kinds of PathElement are described in tbl. 4.
| Constructor | Description | Example |
|---|---|---|
MoveTo(Point) |
Move the pen to Point without drawing. |
MoveTo(cartesian(1, 1)) |
LineTo(Point) |
Draw a straight line to Point |
LineTo(cartesian(2, 2)) |
BezierCurveTo(Point, Point, Point) |
Draw a curve. The first two points specify control points and the last point is where the curve ends. | BezierCurveTo(cartesian(1,0), cartesian(0,1), cartesian(1,1)) |
Constructing a List is straight-forward: we just call List with the elements we want the list to contain. Here are some examples.
// List of Int
List(1, 2, 3)
// List of Image
List(circle(10), circle(20), circle(30))
// List of Color
List(Color.paleGoldenrod, Color.paleGreen, Color.paleTurquoise)
Notice the type of a List includes the type of the elements, written in square brackets. So the type of a list of integers is written List[Int] and a list of PathElement is written List[PathElement].
Exercises
Polygons
Create paths to define a triangle, square, and pentagon. Your image might look like fig. 26. Hint: you might find it easier to use polar coordinates to define the polygons.
Figure 26: A triangle, square, and pentagon, defined using paths.
Using polar coordinates makes it much simpler to define the location of the “corners” (vertices) of the polygons. Each vertex is located a fixed rotation from the previous vertex, and after we’ve marked all vertices we must have done a full rotation of the circle. This means, for example, that for a pentagon each vertex is (360 / 5) = 72 degrees from the previous one. If we start at 0 degrees, vertices are located at 0, 72, 144, 216, and 288 degrees. The distance from the origin is fixed in each case. We don’t have to draw a line between the final vertex and the start—by using a closed path this will be done for us.
Here’s our code to draw fig. 26, which uses this idea. In some cases we haven’t started the vertices at 0 degrees so we can rotate the shape we draw.
import doodle.core.Point._
import doodle.core.Color._
val triangle =
closedPath(List(
MoveTo(polar(50, 0.degrees)),
LineTo(polar(50, 120.degrees)),
LineTo(polar(50, 240.degrees))
))
val square =
closedPath(List(
MoveTo(polar(50, 45.degrees)),
LineTo(polar(50, 135.degrees)),
LineTo(polar(50, 225.degrees)),
LineTo(polar(50, 315.degrees))
))
val pentagon =
closedPath((List(
MoveTo(polar(50, 72.degrees)),
LineTo(polar(50, 144.degrees)),
LineTo(polar(50, 216.degrees)),
LineTo(polar(50, 288.degrees)),
LineTo(polar(50, 360.degrees))
)))
val spacer =
rectangle(10, 100).noLine.noFill
def style(image: Image): Image =
image.lineWidth(6.0).lineColor(paleTurquoise).fillColor(turquoise)
val image =
style(triangle) beside spacer beside style(square) beside spacer beside style(pentagon)
Curves
Repeat the exercise above, but this time use curves instead of straight lines to create some interesting shapes. Our curvy polygons are shown in fig. 27. Hint: you’ll have an easier time if you abstract into a method your code for creating a curve.
Figure 27: A curvy triangle, square, and polygon, defined using paths.
The core of the exercise is to replace the LineTo expressions with BezierCurveTo. We can abstract curve creation into a method that takes the starting angle and the angle increment, and constructs control points at predetermined points along the rotation. This is what we did in the method curve below, and it gives us consistent looking curves without having to manually repeat the calculations each time. Making this abstraction also makes it easier to play around with different control points to create different outcomes.
import doodle.core.Point._
import doodle.core.Color._
def curve(radius: Int, start: Angle, increment: Angle): PathElement = {
BezierCurveTo(
polar(radius * .8, start + (increment * .3)),
polar(radius * 1.2, start + (increment * .6)),
polar(radius, start + increment)
)
}
val triangle =
closedPath(List(
MoveTo(polar(50, 0.degrees)),
curve(50, 0.degrees, 120.degrees),
curve(50, 120.degrees, 120.degrees),
curve(50, 240.degrees, 120.degrees)
))
val square =
closedPath(List(
MoveTo(polar(50, 45.degrees)),
curve(50, 45.degrees, 90.degrees),
curve(50, 135.degrees, 90.degrees),
curve(50, 225.degrees, 90.degrees),
curve(50, 315.degrees, 90.degrees)
))
val pentagon =
closedPath((List(
MoveTo(polar(50, 72.degrees)),
curve(50, 72.degrees, 72.degrees),
curve(50, 144.degrees, 72.degrees),
curve(50, 216.degrees, 72.degrees),
curve(50, 288.degrees, 72.degrees),
curve(50, 360.degrees, 72.degrees)
)))
val spacer =
rectangle(10, 100).noLine.noFill
def style(image: Image): Image =
image.lineWidth(6.0).lineColor(paleTurquoise).fillColor(turquoise)
val image = style(triangle) beside spacer beside style(square) beside spacer beside style(pentagon)
9.2 Working with Lists
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
At this point you might be thinking it would be nice to create a method to draw polygons rather than constructing each one by hand. There is clearly a repeating pattern to their construction and we should be able to abstact this pattern but we don’t know how to create a list of arbitrary size. It’s time we learned more about building and manipulating lists.
9.2.1 The Recursive Structure of Lists
You’ll recall when we introduced structural recursion over the natural numbers we said we could transform their recursive structure into any other recursive structure. We demonstrated this for concentric circles and a variety of other patterns.
Lists have a recursive structure, and one that is very similar to the structure of the natural numbers. A List is
- the empty list
Nil; or - a pair of an element
aand aList, writtena :: tail, wheretailis the rest of the list.
For example, we can write out the list List(1, 2, 3, 4) in its “long” form as
1 :: 2 :: 3 :: 4 :: Nil
Notice the similarity to the natural numbers. Earlier we noted we can expand the structure of a natural number so we could write, say, 3 as 1 + 1 + 1 + 0. If we replace + with :: and 0 with Nil we get the List 1 :: 1 :: 1 :: Nil.
What does this mean? It means we can easily transform a natural number into a List using our famililar tool of structural recursion4. Here’s a very simple example, which given a number builds a list of that length containing the String “Hi”.
def sayHi(length: Int): List[String] =
length match {
case 0 => Nil
case n => "Hi" :: sayHi(n - 1)
}
sayHi(5)
This recursive structure also means we can transform lists into other recursive structures, such a natural numbers, different lists, chessboards, and so on. Here we increment every element a list—that is, transform a list to a list—using structural recursion.
def increment(list: List[Int]): List[Int] =
list match {
case Nil => Nil
case hd :: tl => (hd + 1) :: tl
}
increment(List(1, 2, 3))
Here we sum the elements of a list of integers—that is, transform a list to a natural number—using structural recursion.
def sum(list: List[Int]): Int =
list match {
case Nil => 0
case hd :: tl => hd + sum(tl)
}
sum(List(1, 2, 3))
9.2.2 Type Variables
What about finding the length of a list? We know we can use our standard tool of structural recursion to write the method. Here’s the code to calculate the length of a List[Int].
def length(list: List[Int]): Int =
list match {
case Nil => 0
case hd :: tl => 1 + length(tl)
}
Note that we don’t do anything with the elements of the list—we don’t really care about their type. Using the same code skeleton can just as easily calculate the length of a List[Int] as a List[HairyYak] but we don’t currently know how to write down the type of a list where we don’t care about the type of the elements.
Scala lets us write methods that can work with any type, by using what is called a type variable. A type variable is written in square brackets like [A] and comes after the method name and before the parameter list. A type variable can stand in for any specific type, and we can use it in the parameter list or result type to indicate some type that we don’t know up front. For example, here’s how we can write length so it works with lists of any type.
def length[A](list: List[A]): Int =
list match {
case Nil => 0
case hd :: tl => 1 + length(tl)
}
Structural Recursion over a List
A List of elements of type A is:
- the empty list
Nil; or - an element
aof typeAand atailof typeList[A]:a :: tail
The structural recursion skeleton for transforming list of type List[A] has shape
def doSomething[A,B](list: List[A]): B =
list match {
case Nil => ??? // Base case of type B here
case hd :: tl => f(hd, doSomething(tl))
}
where f is a problem specific method combining hd and result of the recursive call to produce something of type B.
Exercises
Building Lists
In these exercises we get some experience constructing lists using structural recursion on the natural numbers.
Write a method called ones that accepts an Int n and returns a List[Int] with length n and every element 1. For example
def ones(n: Int): List[Int] =
n match {
case 0 => Nil
case n => 1 :: ones(n - 1)
}
ones(3)
It’s structural recursion over the natural numbers!
def ones(n: Int): List[Int] =
n match {
case 0 => Nil
case n => 1 :: ones(n - 1)
}
ones(3)
Write a method descending that accepts an natural number n and returns a List[Int] containing the natural numbers from n to 1 or the empty list if n is zero. For example
def descending(n: Int): List[Int] =
n match {
case 0 => Nil
case n => n :: descending(n - 1)
}
descending(0)
descending(3)
Once more, we can employ structural recursion over the natural numbers.
def descending(n: Int): List[Int] =
n match {
case 0 => Nil
case n => n :: descending(n - 1)
}
descending(0)
descending(3)
Write a method ascending that accepts a natural number n and returns a List[Int] containing the natural numbers from 1 to n or the empty list if n is zero.
def ascending(n: Int): List[Int] = {
def iter(n: Int, counter: Int): List[Int] =
n match {
case 0 => Nil
case n => counter :: iter(n - 1, counter + 1)
}
iter(n, 1)
}
ascending(0)
ascending(3)
It’s structural recursion over the natural numbers, but this time with an internal accumulator.
def ascending(n: Int): List[Int] = {
def iter(n: Int, counter: Int): List[Int] =
n match {
case 0 => Nil
case n => counter :: iter(n - 1, counter + 1)
}
iter(n, 1)
}
ascending(0)
ascending(3)
Create a method fill that accepts a natural number n and an element a of type A and constructs a list of length n where all elements are a.
def fill[A](n: Int, a: A): List[A] =
n match {
case 0 => Nil
case n => a :: fill(n-1, a)
}
fill(3, "Hi")
fill(3, Color.blue)
In this exercise we’re asking you to use a type variable. Otherwise it is the same pattern as before.
def fill[A](n: Int, a: A): List[A] =
n match {
case 0 => Nil
case n => a :: fill(n-1, a)
}
fill(3, "Hi")
fill(3, Color.blue)
Transforming Lists
In these exercises we practice the other side of list manipulation—transforming lists into elements of other types (and sometimes, into different lists).
Write a method double that accepts a List[Int] and returns a list with each element doubled.
def double(list: List[Int]): List[Int] =
list match {
case Nil => Nil
case hd :: tl => (hd * 2) :: double(tl)
}
double(List(1, 2, 3))
double(List(4, 9, 16))
This is a structural recursion over a list, building a list at each step. The destructuring of the input is mirrored by the construction of the output.
def double(list: List[Int]): List[Int] =
list match {
case Nil => Nil
case hd :: tl => (hd * 2) :: double(tl)
}
double(List(1, 2, 3))
double(List(4, 9, 16))
Write a method product that accepts a List[Int] and calculates the product of all the elements.
def product(list: List[Int]): Int =
list match {
case Nil => 1
case hd :: tl => hd * product(tl)
}
product(Nil)
product(List(1,2,3))
This is a structural recursion over a list using the same pattern as sum in the examples above.
def product(list: List[Int]): Int =
list match {
case Nil => 1
case hd :: tl => hd * product(tl)
}
product(Nil)
product(List(1,2,3))
Write a method contains that accepts a List[A] and an element of type A and returns true if the list contains the element and false otherwise.
def contains[A](list: List[A], elt: A): Boolean =
list match {
case Nil => false
case hd :: tl => (hd == elt) || contains(tl, elt)
}
contains(List(1,2,3), 3)
contains(List("one", "two", "three"), "four")
Same pattern as before, but using a type variable to allow type of the elements to vary.
def contains[A](list: List[A], elt: A): Boolean =
list match {
case Nil => false
case hd :: tl => (hd == elt) || contains(tl, elt)
}
contains(List(1,2,3), 3)
contains(List("one", "two", "three"), "four")
Write a method first that accepts a List[A] and an element of type A and returns the first element of the list if it is not empty and otherwise returns the element of type A passed as a aprameter.
def first[A](list: List[A], elt: A): A =
list match {
case Nil => elt
case hd :: tl => hd
}
first(Nil, 4)
first(List(1,2,3), 4)
This method is similar to contains above, except we now use the type variable in the return type as well as in the parameter types.
def first[A](list: List[A], elt: A): A =
list match {
case Nil => elt
case hd :: tl => hd
}
first(Nil, 4)
first(List(1,2,3), 4)
Challenge Exercise: Reverse
Write a method reverse that accepts a List[A] and reverses the list.
def reverse[A](list: List[A]): List[A] = {
def iter(list: List[A], reversed: List[A]): List[A] =
list match {
case Nil => reversed
case hd :: tl => iter(tl, hd :: reversed)
}
iter(list, Nil)
}
reverse(List(1, 2, 3))
reverse(List("a", "b", "c"))
The trick here is to use an accumulator to hold the partially reversed list. If you managed to work this one out, congratulations—you really understand structural recursion well!
def reverse[A](list: List[A]): List[A] = {
def iter(list: List[A], reversed: List[A]): List[A] =
list match {
case Nil => reversed
case hd :: tl => iter(tl, hd :: reversed)
}
iter(list, Nil)
}
reverse(List(1, 2, 3))
reverse(List("a", "b", "c"))
Polygons!
At last, let’s return to our example of drawing polygons. Write a method polygon that accepts the number of sides of the polygon and the starting rotation and produces a Image representing the specified regular polygon. Hint: use an internal accumulator.
Use this utility to create an interesting picture combining polygons. Our rather unimaginative example is in fig. 28. We’re sure you can do better.
Figure 28: Concentric polygons with pastel gradient fill.
Here’s our code. Note how we factored the code into small components—though we could have taken the factoring further is we wanted to. (Can you see how? Hint: do we need to pass, say, start to every call of makeColor when it’s not changing?)
import Point._
def polygon(sides: Int, size: Int, initialRotation: Angle): Image = {
def iter(n: Int, rotation: Angle): List[PathElement] =
n match {
case 0 =>
Nil
case n =>
LineTo(polar(size, rotation * n + initialRotation)) :: iter(n - 1, rotation)
}
closedPath(MoveTo(polar(size, initialRotation)) :: iter(sides, 360.degrees / sides))
}
def style(img: Image): Image = {
img.
lineWidth(3.0).
lineColor(Color.mediumVioletRed).
fillColor(Color.paleVioletRed.fadeOut(0.5.normalized))
}
def makeShape(n: Int, increment: Int): Image =
polygon(n+2, n * increment, 0.degrees)
def makeColor(n: Int, spin: Angle, start: Color): Color =
start spin (spin * n)
val baseColor = Color.hsl(0.degrees, 0.7.normalized, 0.7.normalized)
def makeImage(n: Int): Image = {
n match {
case 0 =>
Image.empty
case n =>
val shape = makeShape(n, 10)
val color = makeColor(n, 30.degrees, baseColor)
makeImage(n-1) on (shape fillColor color)
}
}
val image = makeImage(15)
9.3 Transforming Sequences
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
We’ve seen that using structural recursion we can create and transform lists. This pattern is simple to use and to understand, but it requires we write the same skeleton time and again. In this section we’ll learn that we can replace structural recursion in some cases by using a method on List called map. We’ll also see that other useful datatypes provide this method and we can use it as a common interface for manipulating sequences.
9.3.1 Transforming the Elements of a List
In the previous section we say several examples where we transformed one list to another. For example, we incremented the elements of a list with the following code.
def increment(list: List[Int]): List[Int] =
list match {
case Nil => Nil
case hd :: tl => (hd + 1) :: tl
}
increment(List(1, 2, 3))
In this example the structure of the list doesn’t change. If we start with three elements we end with three elements. We can abstract this pattern in a method called map. If we have a list with elements of type A, we pass map a function of type A => B and we get back a list with elements of type B. For example, we can implement increment using map with the function x => x + 1.
def increment(list: List[Int]): List[Int] =
list.map(x => x + 1)
increment(List(1, 2, 3))
Each element is transformed by the function we pass to map, in this case x => x + 1. With map we can transform the elements, but we cannot change the number of elements in the list.
We find a graphical notation helps with understanding map. If we had some type Circle we can draw a List[Circle] as a box containing a circle, as shown in fig. 29.
Figure 29: A List[Circle] representing by a circle within a box
Now we can draw an equation for map as in fig. 30. If you prefer symbols instead of pictures, the picture is showing that List[Circle] map (Circle => Triangle) = List[Triangle]. One feature of the graphical representation is it nicely illustrates that map cannot create a new “box”, which represents the structure of the list—or more concretely the number of elements and their order.
Figure 30: map shown graphically
The graphical drawing of map exactly illustrates what holds at the type level for map. If we prefer we can write it down symbolically:
List[A] map (A => B) = List[B]The left hand side of the equation has the type of the list we map and the function we use to do the mapping. The right hand is the type of the result. We can perform algebra with this reprsentation, substituting in concrete types from our program.
9.3.2 Transforming Sequences of Numbers
We have also written a lot of methods that transform a natural number to a list. We briefly discussed how we can represent a natural number as a list. 3 is equivalent to 1 + 1 + 1 + 0, which in turn we could represent as List(1, 1, 1). So what? Well, it means we could write a lot of the methods that accepts natural numbers as methods that worked on lists.
For example, instead of
def fill[A](n: Int, a: A): List[A] =
n match {
case 0 => Nil
case n => a :: fill(n-1, a)
}
fill(3, "Hi")
we could write
def fill[A](n: List[Int], a: A): List[A] =
n.map(x => a)
fill(List(1, 1, 1), "Hi")
The implementation of this version of fill is more convenient to write, but it is much less convenient for the user to call it with List(1, 1, ,1) than just writing 3.
If we want to work with sequences of numbers we are better off using Ranges. We can create these using the until method of Int or Double:
0 until 10
0.0 until 5.0
Ranges have a by method that allows us to change the step between consecutive elements of the range:
0 until 10 by 2
0.0 until 1.0 by 0.3
Ranges also have a map method just like List
(0 until 3) map (x => x + 1)
You’ll notice the result has type IndexedSeq and is implemented as a Vector—two types we haven’t seen yet. We can treat an IndexedSeq much like a List, but for simplicity we can convert a Range or an IndexedSeq to a List using the toList method.
(0 until 7).toList
(0 until 3).map(x => x + 1).toList
With Ranges in our toolbox we can write fill as
def fill[A](n: Int, a: A): List[A] =
(0 until n).toList.map(x => a)
fill(3, "Hi")
Exercises
Ranges, Lists, and map
Using our new tools, reimplement the following methods.
Write a method called ones that accepts an Int n and returns a List[Int] with length n and every element is 1. For example
def ones(n: Int): List[Int] =
(0 until n).toList.map(x => 1)
ones(3)
We can just map over a Range to achieve this.
def ones(n: Int): List[Int] =
(0 until n).toList.map(x => 1)
ones(3)
Write a method descending that accepts an natural number n and returns a List[Int] containing the natural numbers from n to 1 or the empty list if n is zero. For example
def descending(n: Int): List[Int] =
(n until 0 by -1).toList
descending(0)
descending(3)
We can use a Range but we have to set the step size or the range will be empty.
def descending(n: Int): List[Int] =
(n until 0 by -1).toList
descending(0)
descending(3)
Write a method ascending that accepts a natural number n and returns a List[Int] containing the natural numbers from 1 to n or the empty list if n is zero.
def ascending(n: Int): List[Int] =
(0 until n).toList.map(x => x + 1)
ascending(0)
ascending(3)
Again we can use a Range but we need to take care to start at 0 and increment the elements by 1 so we have the correct number of elements.
def ascending(n: Int): List[Int] =
(0 until n).toList.map(x => x + 1)
ascending(0)
ascending(3)
Write a method double that accepts a List[Int] and returns a list with each element doubled.
def double(list: List[Int]): List[Int] =
list map (x => x * 2)
double(List(1, 2, 3))
double(List(4, 9, 16))
This is a straightforward application of map.
def double(list: List[Int]): List[Int] =
list map (x => x * 2)
double(List(1, 2, 3))
double(List(4, 9, 16))
Polygons, Again!
Using our new tools, rewrite the polygon method from the previous section.
Here’s one possible implementation. Much easier to read than the previous implementation!
def polygon(sides: Int, size: Int, initialRotation: Angle): Image = {
import Point._
val step = (Angle.one / sides).toDegrees
val path =
(0.0 to 360.0 by step).toList.map{ deg =>
LineTo(polar(size, initialRotation + deg.degrees))
}
closedPath(MoveTo(polar(size, initialRotation)) :: path)
}
Challenge Exercise: Beyond Map
Can we use map to replace all uses of structural recursion? If not, can you characterise the problems that we can’t implement with map but can implement with general structural recursion over lists?
We’ve seen many examples that we cannot implement with map: the methods product, sum, find, and more in the previous section cannot be implemented with map.
In abstract, methods implemented with map obey the following equation:
List[A] map A => B = List[B]If the result is not of type List[B] we cannot implement it with map. For example, methods like product and sum transform List[Int] to Int and so cannot be implemented with map.
Map transforms the elements of a list, but cannot change the number of elements in the result. Even if a method fits the equation for map above it cannot be implemented with map if it requires changing the number of elements in the list.
9.3.3 Tools with Ranges
We’ve seen the until method to construct Ranges, and the by method to change the increment in a Range. There is one more method that will be useful to know about: to. This constructs a Range like until but the Range includes the endpoint. Compare
1 until 5
1 to 5
In technical terms, the Range constructed with until is a half-open interval, while the range constructed with to is an open interval.
Exercises
Using Open Intervals
Write a method ascending that accepts a natural number n and returns a List[Int] containing the natural numbers from 1 to n or the empty list if n is zero. Hint: use to
def ascending(n: Int): List[Int] =
(1 to n).toList
ascending(0)
ascending(3)
Now that we now about to this is trivial to implement.
def ascending(n: Int): List[Int] =
(1 to n).toList
ascending(0)
ascending(3)
9.4 My God, It’s Full of Stars!
import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
Let’s use our new tools to draw some stars. For the purpose of this exercise let’s assume that a star is a polygon with p points. However, instead of connecting each point to its neighbours, we’ll connect them to the nth point around the circumference.
For example, fig. 31 shows stars with p=11 and n=1 to 5. n=1 produces a regular polygon while values of n from 2 upwards produce stars with increasingly sharp points:
Figure 31: Stars with p=11 and n=1 to 5
Write code to draw the diagram above. Start by writing a method to draw a star given p and n:
def star(p: Int, n: Int, radius: Double): Image =
???
Hint: use the same technique we used for polygon previously.
Here’s the star method. We’ve renamed p and n to points and skip for clarity:
def star(sides: Int, skip: Int, radius: Double): Image = {
import Point._
val rotation = 360.degrees * skip / sides
val start = MoveTo(polar(radius, 0.degrees))
val elements = (1 until sides).toList map { index =>
val point = polar(radius, rotation * index)
LineTo(point)
}
closedPath(start :: elements) lineWidth 2
}
Using structural recursion and beside write a method allBeside with the signature
def allBeside(images: List[Image]): Image =
???
We’ll use allBeside to create the row of stars. To create the picture we only need to use values of skip from 1 to sides/2 rounded down. For example:
def allBeside(imgs: List[Image]): Image =
imgs match {
case Nil => Image.empty
case hd :: tl => hd beside allBeside(tl)
}
allBeside(
(1 to 5).toList map { skip =>
star(11, skip, 100)
}
)